{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Circular Array Loop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: circularArrayLoop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形数组是否存在循环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个不含 <code>0</code> 的<strong> 环形 </strong>数组&nbsp;<code>nums</code> ，每个 <code>nums[i]</code> 都表示位于下标 <code>i</code> 的角色应该向前或向后移动的下标个数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>nums[i]</code> 是正数，<strong>向前</strong>（下标递增方向）移动 <code>|nums[i]|</code> 步</li>\n",
    "\t<li>如果&nbsp;<code>nums[i]</code> 是负数，<strong>向后</strong>（下标递减方向）移动 <code>|nums[i]|</code> 步</li>\n",
    "</ul>\n",
    "\n",
    "<p>因为数组是 <strong>环形</strong> 的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。</p>\n",
    "\n",
    "<p>数组中的 <strong>循环</strong> 由长度为 <code>k</code> 的下标序列 <code>seq</code> 标识：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>遵循上述移动规则将导致一组重复下标序列 <code>seq[0] -&gt; seq[1] -&gt; ... -&gt; seq[k - 1] -&gt; seq[0] -&gt; ...</code></li>\n",
    "\t<li>所有 <code>nums[seq[j]]</code> 应当不是 <strong>全正</strong> 就是 <strong>全负</strong></li>\n",
    "\t<li><code>k &gt; 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>如果 <code>nums</code> 中存在循环，返回 <code>true</code> ；否则，返回<em> </em><code>false</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,-1,1,2,2]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>存在循环，按下标 0 -&gt; 2 -&gt; 3 -&gt; 0 。循环长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>按下标 1 -&gt; 1 -&gt; 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-2,1,-1,-2,-2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>按下标 1 -&gt; 2 -&gt; 1 -&gt; ... 的运动无法构成循环，因为 nums[1] 是正数，而 nums[2] 是负数。\n",
    "所有 nums[seq[j]] 应当不是全正就是全负。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5000</code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>nums[i] != 0</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能设计一个时间复杂度为 <code>O(n)</code> 且额外空间复杂度为 <code>O(1)</code> 的算法吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [circular-array-loop](https://leetcode.cn/problems/circular-array-loop/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [circular-array-loop](https://leetcode.cn/problems/circular-array-loop/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,-1,1,2,2]', '[-1,-2,-3,-4,-5,6]', '[1,-1,5,1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        def getNext(i):\n",
    "            return (n + nums[i] + i) % n\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                continue\n",
    "            slow = i\n",
    "            fast = getNext(slow)\n",
    "\n",
    "            while nums[slow] * nums[fast] > 0 and nums[fast] * nums[getNext(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == getNext(slow):\n",
    "                        break\n",
    "                    return True\n",
    "\n",
    "                slow = getNext(slow)\n",
    "                fast = getNext(getNext(fast))\n",
    "\n",
    "            j = i\n",
    "            while nums[j] * nums[getNext(j)] > 0:\n",
    "                tmp = j\n",
    "                j = getNext(j)\n",
    "                nums[tmp] = 0\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "# 双指针 O(n2)\n",
    "# class Solution:\n",
    "#     def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "#         def getNext(i):\n",
    "#             # n = len(nums)\n",
    "#             return (i + nums[i] + n) % n\n",
    "\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             slow = i\n",
    "#             fast = getNext(slow)\n",
    "\n",
    "#             while nums[slow] * nums[fast] > 0 and nums[fast] * nums[getNext(fast)] > 0:\n",
    "#                 if slow == fast:\n",
    "#                     if slow == getNext(slow):\n",
    "#                         break\n",
    "#                     return True\n",
    "#                 slow = getNext(slow)\n",
    "#                 fast = getNext(getNext(fast))\n",
    "#         return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        res = False\n",
    "        seqs = []\n",
    "        n = len(nums)\n",
    "        if n==1 :\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            seq = []\n",
    "            flag = nums[i]/abs(nums[i])\n",
    "            cur = i \n",
    "            while(True):                \n",
    "                next_ind = (cur + nums[cur])%n \n",
    "                if nums[cur]*flag<0:\n",
    "                    break\n",
    "                \n",
    "                seq.append(cur)\n",
    "                if next_ind == i:\n",
    "                    if len(seq)>1:\n",
    "                        res = True\n",
    "                    break \n",
    "                if next_ind in seq:\n",
    "                    break\n",
    "                cur = next_ind\n",
    "            print(seq)\n",
    "            if  res:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "\n",
    "        def next(cur):\n",
    "            return (cur+nums[cur])%n\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if num==0:continue\n",
    "\n",
    "            slow,fast=i,next(i)\n",
    "            #判断非零且方向相同\n",
    "            while nums[slow]*nums[fast]>0 and nums[slow]*nums[next(fast)]>0 :\n",
    "                if slow==fast:\n",
    "                    if slow ==next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow=next(slow)\n",
    "                fast=next(next(fast))\n",
    "            add=i\n",
    "            while nums[add]*nums[next(add)]>0:\n",
    "                tmp=add\n",
    "                add=next(add)\n",
    "                nums[tmp]=0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        def getNext(i):\n",
    "            # n = len(nums)\n",
    "            return (i + nums[i] + n) % n\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            slow = i\n",
    "            fast = getNext(slow)\n",
    "\n",
    "            while nums[slow] * nums[fast] > 0 and nums[fast] * nums[getNext(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == getNext(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = getNext(slow)\n",
    "                fast = getNext(getNext(fast))\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur: int) -> int:\n",
    "            return (cur + nums[cur]) % n\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0: continue\n",
    "            slow, fast = i, next(i)\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    else:\n",
    "                        return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                tmp = add\n",
    "                add = next(add)\n",
    "                nums[tmp] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        def getNext(i):\n",
    "            return (n + nums[i] + i) % n\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            slow = i\n",
    "            fast = getNext(slow)\n",
    "\n",
    "            while nums[slow] * nums[fast] > 0 and nums[fast] * nums[getNext(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == getNext(slow):\n",
    "                        break\n",
    "                    return True\n",
    "\n",
    "                slow = getNext(slow)\n",
    "                fast = getNext(getNext(fast))\n",
    "        return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "#         def getNext(i):\n",
    "#             # n = len(nums)\n",
    "#             return (i + nums[i] + n) % n\n",
    "\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             slow = i\n",
    "#             fast = getNext(slow)\n",
    "\n",
    "#             while nums[slow] * nums[fast] > 0 and nums[fast] * nums[getNext(fast)] > 0:\n",
    "#                 if slow == fast:\n",
    "#                     if slow == getNext(slow):\n",
    "#                         break\n",
    "#                     return True\n",
    "#                 slow = getNext(slow)\n",
    "#                 fast = getNext(getNext(fast))\n",
    "#         return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "  \n",
    "class Solution(object):\n",
    "    def circularArrayLoop(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        N, self.nums = len(nums), nums\n",
    "        for i in range(N):\n",
    "            slow = i\n",
    "            fast = self.nextpos(slow)\n",
    "            while nums[fast] * nums[i] > 0 and nums[self.nextpos(fast)] * nums[i] > 0:\n",
    "                if fast == slow:\n",
    "                    if slow == self.nextpos(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = self.nextpos(slow)\n",
    "                fast = self.nextpos(self.nextpos(fast))\n",
    "        return False\n",
    "    \n",
    "    def nextpos(self, index):\n",
    "        N = len(self.nums)\n",
    "        return (index + self.nums[index] ) % N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        length = len(nums)\n",
    "        visited = set()\n",
    "        flag = set()\n",
    "        \n",
    "        def dfs(i):\n",
    "            visited.add(i)\n",
    "            next_i = (i + nums[i]) % length\n",
    "            if (i not in flag) and ((nums[i] > 0) == (nums[next_i] > 0)):\n",
    "                if next_i in visited:\n",
    "                    if next_i == i:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return True\n",
    "                else:\n",
    "                    return dfs(next_i)\n",
    "            return False\n",
    "        \n",
    "        for i in range(length):\n",
    "            flag |= visited\n",
    "            visited = set()\n",
    "            if dfs(i):\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        l_len=len(nums)\n",
    "        for j in range(len(nums)):\n",
    "            #print(j)\n",
    "            direction=nums[j]\n",
    "            step_list=[]\n",
    "            i=j\n",
    "            while 1:\n",
    "                if nums[i]*direction<0:\n",
    "                    break\n",
    "                step_list.append(i)\n",
    "                i_next=(i+nums[i])%l_len\n",
    "                if i_next in step_list:\n",
    "                    if i_next!=step_list[-1]:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                i=i_next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def circularArrayLoop(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        def nextPos(idx):\n",
    "            return (idx+nums[idx])%n\n",
    "        \n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            slow = i\n",
    "            fast = nextPos(i)\n",
    "            while nums[i]*nums[fast]>0 and nums[i]*nums[nextPos(fast)] >0:\n",
    "                if fast == slow:\n",
    "                    if slow == nextPos(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = nextPos(slow)\n",
    "                fast = nextPos(nextPos(fast))\n",
    "        return False                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            mark = str(i)\n",
    "\n",
    "\n",
    "\n",
    "            while (type(nums[i]) == int) and (num * nums[i] > 0) and (nums[i] % len(nums) != 0):\n",
    "                # 三个约束，分别是防止重复跳跃到该位置、要求同号、防止环长度为1（跳回原来的位置）\n",
    "                \n",
    "                jump = nums[i]\n",
    "\n",
    "                nums[i] = mark #跳过的置为字符，用于拦截重复到该位置\n",
    "\n",
    "                i = (i + jump) % len(nums) # 跳跃\n",
    "\n",
    "\n",
    "\n",
    "            if nums[i] == mark: #如果跳回了最初位置，则相等，形成环。不相等表示条件不满足，寄\n",
    "\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        # 用哈希\n",
    "        # 快慢指针\n",
    "        n = len(nums)\n",
    "        # 下一个位置\n",
    "        nx = lambda x: (x+nums[x])%n\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:continue\n",
    "            slow  = i\n",
    "            fast = nx(i)\n",
    "            while nums[slow]*nums[fast]>0 and nums[fast]*nums[nx(fast)]>0:\n",
    "                if slow == fast:\n",
    "                    if slow == nx(slow):\n",
    "                        break\n",
    "                    else:\n",
    "                        return True\n",
    "                slow = nx(slow)\n",
    "                fast = nx(nx(fast))\n",
    "            val = nums[i]\n",
    "            while val*nums[i] > 0:\n",
    "                tm = nx(i)\n",
    "                nums[i] = 0\n",
    "                i = tm\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        change = True\n",
    "\n",
    "        while change:\n",
    "            change = False\n",
    "            for i, num in enumerate(nums):\n",
    "                if not num:\n",
    "                    continue\n",
    "                \n",
    "                nxt = (i+num)%n\n",
    "\n",
    "                if nxt == i or nums[nxt]*num<=0:\n",
    "                    nums[i] = 0\n",
    "                    change = True\n",
    "        \n",
    "\n",
    "\n",
    "        for i in nums:\n",
    "            if i!=0:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        判断环形都可以使用快慢指针处理\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        def nxtf(i):\n",
    "            return (i + nums[i]) % n\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                continue\n",
    "            slow = i\n",
    "            fast = nxtf(i)\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow]*nums[nxtf(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == nxtf(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = nxtf(slow)\n",
    "                fast = nxtf(nxtf(fast))\n",
    "            slow = i\n",
    "            # 注意转折点可能是另一条路径的，因此我们只置零前半部分\n",
    "            while nums[slow] * nums[nxtf(slow)] > 0:\n",
    "                tmp = slow\n",
    "                slow = nxtf(slow)\n",
    "                nums[tmp] = 0\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur: int) -> int:\n",
    "            return (cur + nums[cur]) % n  # 保证返回值在 [0,n) 中\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, next(i)\n",
    "            # 判断非零且方向相同\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                tmp = add\n",
    "                add = next(add)\n",
    "                nums[tmp] = 0\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        def nxt(i):\n",
    "            return (i + nums[i]) % n\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, nxt(i)\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[nxt(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == nxt(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = nxt(slow)\n",
    "                fast = nxt(nxt(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[nxt(add)] > 0:\n",
    "                tmp = add\n",
    "                add = nxt(add)\n",
    "                nums[tmp] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur):\n",
    "            return (cur + nums[cur]) % n  # 保证下标在 [0,n) 范围内\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, next(i)\n",
    "            # 判断非零且方向相同\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                nums[add] = 0\n",
    "                add = next(add)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        def next(cur):\n",
    "            return (cur+nums[cur]) % n\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow = i\n",
    "            fast = next(i)\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                nums[add] = 0\n",
    "                add = next(add)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            slow = i\n",
    "            fast = (slow + nums[slow]) % n\n",
    "            while nums[slow] * nums[fast] > 0 and nums[fast] * nums[(fast+nums[fast]) % n] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == (slow + nums[slow]) % n:\n",
    "                        break\n",
    "                    return True\n",
    "                slow = (slow + nums[slow]) % n\n",
    "                fast = (fast+nums[fast]) % n\n",
    "                fast = (fast+nums[fast]) % n\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        l_len=len(nums)\n",
    "        for j in range(len(nums)):\n",
    "            #print(j)\n",
    "            direction=nums[j]\n",
    "            step_list=[]\n",
    "            i=j\n",
    "            while 1:\n",
    "                if nums[i]*direction<0:\n",
    "                    break\n",
    "                step_list.append(i)\n",
    "                i_next=(i+nums[i])%l_len\n",
    "                if i_next in step_list:\n",
    "                    if i_next!=step_list[-1]:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                i=i_next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            index = []\n",
    "            flag = True\n",
    "            same = nums[i]\n",
    "            while i not in index:\n",
    "                if nums[i] * same<0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                index.append(i)\n",
    "                i += nums[i]\n",
    "                i = i%n\n",
    "            if flag:\n",
    "                j = (i+nums[i])%n\n",
    "                if j!=i:\n",
    "                    res = max(res,len(index))\n",
    "                    if res>1:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        def next(cur):\n",
    "            return (cur+nums[cur]) % n\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if num==0:\n",
    "                continue\n",
    "            slow,fast = i,next(i)\n",
    "\n",
    "            while nums[slow]*nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow==fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            \n",
    "            cu = i\n",
    "            while nums[cu] * nums[next(cu)] > 0:\n",
    "                tmp = cu\n",
    "                cu = next(cu)\n",
    "                nums[cu] = 0\n",
    "            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            index = []\n",
    "            flag = True\n",
    "            same = nums[i]\n",
    "            while i not in index:\n",
    "                if nums[i] * same<0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                index.append(i)\n",
    "                i += nums[i]\n",
    "                i = i%n\n",
    "            if flag:\n",
    "                j = (i+nums[i])%n\n",
    "                if j!=i:\n",
    "                    res = max(res,len(index))\n",
    "        if res>1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            mark = str(i)\n",
    "\n",
    "\n",
    "\n",
    "            while (type(nums[i]) == int) and (num * nums[i] > 0) and (nums[i] % len(nums) != 0):\n",
    "                # 三个约束，分别是防止重复跳跃到该位置、要求同号、防止环长度为1（跳回原来的位置）\n",
    "                \n",
    "                jump = nums[i]\n",
    "\n",
    "                nums[i] = mark #跳过的置为字符，用于拦截重复到该位置\n",
    "\n",
    "                i = (i + jump) % len(nums) # 跳跃\n",
    "\n",
    "\n",
    "\n",
    "            if nums[i] == mark: #如果跳回了最初位置，则相等，形成环。不相等表示条件不满足，寄\n",
    "\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "            (1) 看成图，nums[i] 表示 i 号点向 i+1 号点有一条单向边。\n",
    "            (2) 每个点有且仅有一条出边， 那么从任意一个点出发，一定能走到一个环。\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        def check(start):\n",
    "            flag = nums[start] > 0\n",
    "            curr = start\n",
    "            k = 1\n",
    "            while True:\n",
    "                if k > n: return False\n",
    "                nxt = (curr + nums[curr]) % n\n",
    "                if (nums[nxt] > 0) != flag: return False\n",
    "                if (start == nxt): return k > 1\n",
    "                curr = nxt\n",
    "                k += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if check(i): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def circularArrayLoop(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        N, self.nums = len(nums), nums\n",
    "        for i in range(N):\n",
    "            slow = i\n",
    "            fast = self.nextpos(slow)\n",
    "            while nums[fast] * nums[i] > 0 and nums[self.nextpos(fast)] * nums[i] > 0:\n",
    "                if fast == slow:\n",
    "                    if slow == self.nextpos(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = self.nextpos(slow)\n",
    "                fast = self.nextpos(self.nextpos(fast))\n",
    "        return False\n",
    "    \n",
    "    def nextpos(self, index):\n",
    "        N = len(self.nums)\n",
    "        return (index + self.nums[index]) % N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur: int) -> int:\n",
    "            return (cur + nums[cur]) % n  # 保证返回值在 [0,n) 中\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, next(i)\n",
    "            # 判断非零且方向相同\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                tmp = add\n",
    "                add = next(add)\n",
    "                nums[tmp] = 0\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        for i in range(len(nums)):\n",
    "            seen = set()\n",
    "            cur = i\n",
    "            positive = 0\n",
    "            negative = 0\n",
    "            while cur not in seen:\n",
    "                seen.add(cur)\n",
    "                if nums[cur] > 0: positive = 1\n",
    "                else: negative = 2\n",
    "                cur += nums[cur]\n",
    "                cur %= len(nums)\n",
    "            if cur == i and len(seen) > 1 and positive * negative == 0: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        nxt= lambda x: (x+nums[x])%n\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                continue\n",
    "            slow=i\n",
    "            fast=nxt(i)\n",
    "            while nums[slow]*nums[fast]>0 and nums[fast]*nums[nxt(fast)]>0:\n",
    "                if slow==fast:\n",
    "                    if slow==nxt(slow):\n",
    "                        break\n",
    "                    else:\n",
    "                        return True\n",
    "                slow=nxt(slow)\n",
    "                fast=nxt(nxt(fast))\n",
    "            # val =nums[i]\n",
    "            # while val *nums[i]>0:\n",
    "            #     tmp=nxt(i)\n",
    "            #     nums[i]=0\n",
    "            #     i=tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        nxt= lambda x: (x+nums[x])%n\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                continue\n",
    "            slow=i\n",
    "            fast=nxt(i)\n",
    "            while nums[slow]*nums[fast]>0 and nums[fast]*nums[nxt(fast)]>0:\n",
    "                if slow==fast:\n",
    "                    if slow==nxt(slow):\n",
    "                        break\n",
    "                    else:\n",
    "                        return True\n",
    "                slow=nxt(slow)\n",
    "                fast=nxt(nxt(fast))\n",
    "            val =nums[i]\n",
    "            while val *nums[i]>0:\n",
    "                tmp=nxt(i)\n",
    "                nums[i]=0\n",
    "                i=tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        a=[]\n",
    "        for i in range(n):\n",
    "            #if i in a:\n",
    "                #return True\n",
    "            ii=i\n",
    "            a+=[i]\n",
    "            while True:\n",
    "                i=(i+nums[i])%n\n",
    "                if nums[ii]*nums[i]<0:\n",
    "                    del a[-1]\n",
    "                    break\n",
    "                if i in a:\n",
    "                    if len(a)==1:\n",
    "                        break\n",
    "                    else:\n",
    "                        if i==ii:\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "                a+=[i]\n",
    "            a=[]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "\n",
    "        for i in range(n):\n",
    "            index = []\n",
    "            flag = True\n",
    "            same = nums[i]\n",
    "            while i not in index:\n",
    "                if nums[i] * same<0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                index.append(i)\n",
    "                i += nums[i]\n",
    "                i = i%n\n",
    "            if flag:\n",
    "                j = (i+nums[i])%n\n",
    "                if j!=i:\n",
    "                    if len(index)>1:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef circularArrayLoop(self, nums):\n",
    "\t\tn = len(nums)\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tt = [False] * n\n",
    "\t\t\tx, c = i, [0, 0]\n",
    "\t\t\twhile not t[x]:\n",
    "\t\t\t\tt[x] = True\n",
    "\t\t\t\tx = (x + nums[x]) % n\n",
    "\t\t\tt = [False] * len(nums)\n",
    "\t\t\twhile not t[x]:\n",
    "\t\t\t\tc[0 if nums[x] > 0 else 1] += 1\n",
    "\t\t\t\tt[x] = True\n",
    "\t\t\t\tx = (x + nums[x]) % n\n",
    "\t\t\tif (c[0] > 1 or c[1] > 1) and c[0] * c[1] == 0: return True\n",
    "\t\treturn False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            k = nums[i]\n",
    "            cur = {}\n",
    "            while i not in vis:\n",
    "                vis.add(i)\n",
    "                cur[i] = len(cur)\n",
    "                i = (i + nums[i] % n) % n\n",
    "            if nums[i] % n:\n",
    "                foo = set()\n",
    "                for _ in range(n + 1):\n",
    "                    if nums[i] * k < 0:\n",
    "                        break\n",
    "                    if i in foo and nums[i] % n:\n",
    "                        return True\n",
    "                    foo.add(i)\n",
    "                    i = (i + nums[i] % n) % n\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        b2 = 1005\n",
    "        n = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            if v > 4096:\n",
    "                continue\n",
    "            c = i\n",
    "            i = (i + 1) << 12\n",
    "            f = 1 if v > 0 else -1\n",
    "            while nums[c] < 4096 and nums[c] * f > 0:\n",
    "                v = nums[c]\n",
    "                nums[c] = i + v + b2\n",
    "                c = (c + v) % n\n",
    "            if nums[c] > 4096 and nums[c] >> 12 == i >> 12:\n",
    "                if (c + (nums[c] % 4096 - b2)) % n != c:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        # 快慢指针？\n",
    "        # 限制条件：只能单向移动\n",
    "        N = len(nums)\n",
    "        def nextpos(index):\n",
    "            return (index + nums[index] + N) % N\n",
    "        \n",
    "        def judge(pos):\n",
    "            direction = nums[pos]\n",
    "            slow = pos\n",
    "            fast = nextpos(pos)\n",
    "            while nums[fast]*direction>0 and nums[nextpos(fast)]*direction>0:\n",
    "                if fast==slow:\n",
    "                    return slow!=nextpos(slow) # 避免单个元素循环\n",
    "                slow = nextpos(slow)\n",
    "                fast = nextpos(fast)\n",
    "                fast = nextpos(fast)\n",
    "            return False\n",
    "\n",
    "\n",
    "        for i in range(N):\n",
    "            if judge(i):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \n",
    "       \n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            new_key=(n+nums[i]+i)%n\n",
    "            key=i\n",
    "            list1=[i]\n",
    "            flag=True\n",
    "            while new_key not in list1:\n",
    "                if new_key<=i:\n",
    "                    flag=False\n",
    "                    break\n",
    "                if nums[new_key]*nums[key]>0:\n",
    "                    list1.append(new_key)\n",
    "                    key=new_key\n",
    "                    new_key=(n+nums[key]+key)%n\n",
    "                    \n",
    "                else:\n",
    "                    flag=False\n",
    "                    break\n",
    "            \n",
    "                \n",
    "            if flag and len(list1)-1-list1.index(new_key)>=1:\n",
    "                return True\n",
    "        return False\n",
    "                \n",
    "                    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            q = [i]\n",
    "            for _ in range(n):\n",
    "                tmp = (q[-1] + nums[q[-1]]) % n\n",
    "                if tmp == q[-1] or nums[q[-1]] * nums[tmp] < 0:\n",
    "                    break\n",
    "                q.append(tmp)\n",
    "            if len(q) > n: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            q = [i]\n",
    "            for _ in range(n):\n",
    "                tmp = (q[-1] + nums[q[-1]] + n) % n\n",
    "                if tmp == q[-1] or nums[q[-1]] * nums[tmp] < 0:\n",
    "                    break\n",
    "                q.append(tmp)\n",
    "            if len(q) > n: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            q = [i]\n",
    "            for _ in range(n):\n",
    "                tmp = (q[-1] + nums[q[-1]]) % n\n",
    "                if tmp == q[-1] or nums[q[-1]] * nums[tmp] < 0:\n",
    "                    break\n",
    "                q.append(tmp)\n",
    "            if len(q) > n: return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        def next_(i):\n",
    "            return (i + nums[i]) % n\n",
    "        for i, x in enumerate(nums):\n",
    "            slow, fast = i, next_(i)\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next_(fast)] > 0:\n",
    "                if fast == slow:\n",
    "                    if slow == next_(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next_(slow)\n",
    "                fast = next_(next_(fast))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        idx1 = set() #存储所有被查找过的下标\n",
    "        for i in range(len(nums)):\n",
    "            idx2 = set() #存储在当前循环中被查找的下标\n",
    "            next_num = i\n",
    "            while next_num not in idx1 and nums[next_num]*nums[i]>0:\n",
    "                if next_num in idx2:\n",
    "                    if nums[next_num]%(len(nums))!=0:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                idx2.add(next_num)\n",
    "                next_num = (next_num+nums[next_num])%(len(nums))\n",
    "            idx1=idx1.union(idx2)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur: int) -> int:\n",
    "            return (cur + nums[cur]) % n  # 保证返回值在 [0,n) 中\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, next(i)\n",
    "            # 判断非零且方向相同\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            # add = i\n",
    "            # while nums[add] * nums[next(add)] > 0:\n",
    "            #     tmp = add\n",
    "            #     add = next(add)\n",
    "            #     nums[tmp] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                if nums[i]>0:\n",
    "                    direction = 1\n",
    "                else:\n",
    "                    direction = -1\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                num = 0\n",
    "                pre_num = 0\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*direction<0:\n",
    "                            break\n",
    "                        num+=1\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = num\n",
    "                        pos = pos+step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                            if pre_num == len(sign2):\n",
    "                                break\n",
    "                            pre_num = len(sign2)  \n",
    "                    else:\n",
    "                        if sign2[pos]<num:\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \n",
    "       \n",
    "        n=len(nums)\n",
    "        nxt=[(n+nums[i]+i)%n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            new_key=nxt[i]\n",
    "            key=i\n",
    "            list1=[i]\n",
    "            new_key\n",
    "            flag=True\n",
    "            while new_key not in list1:\n",
    "                if new_key<=i:\n",
    "                    flag=False\n",
    "                    break\n",
    "                if nums[new_key]*nums[key]>0:\n",
    "                    list1.append(new_key)\n",
    "                    key=new_key\n",
    "                    new_key=nxt[key]\n",
    "                    \n",
    "                else:\n",
    "                    flag=False\n",
    "                    break\n",
    "            \n",
    "                \n",
    "            if flag and len(list1)-1-list1.index(new_key)>=1:\n",
    "                return True\n",
    "        return False\n",
    "                \n",
    "                    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        idx1 = set()\n",
    "        idx2 = set()\n",
    "        for i in range(len(nums)):\n",
    "            if i in idx1:\n",
    "                continue\n",
    "            next_num = i\n",
    "            while next_num not in idx1 and nums[next_num]*nums[i]>0:\n",
    "                if next_num in idx2:\n",
    "                    if nums[next_num]%(len(nums))!=0:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                idx2.add(next_num)\n",
    "                next_num = (next_num+nums[next_num])%(len(nums))\n",
    "            idx1=idx1.union(idx2)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            sign = 1\n",
    "            if nums[i] < 0:\n",
    "                sign = -1\n",
    "            \n",
    "            if i == (i + n + nums[i]) % n:\n",
    "                continue\n",
    "            \n",
    "            visited = set([i])\n",
    "            cur = i\n",
    "            while True:\n",
    "                nxt = (cur + n + nums[cur]) % n\n",
    "                if nxt == cur:\n",
    "                    break\n",
    "                \n",
    "                if nxt in visited:\n",
    "                    return True\n",
    "                \n",
    "                if sign == 1 and nums[nxt] < 0:\n",
    "                    break\n",
    "                if sign == -1 and nums[nxt] > 0:\n",
    "                    break\n",
    "                \n",
    "                visited.add(nxt)\n",
    "                cur = nxt\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        used=set()\n",
    "        for i in range(len(nums)):\n",
    "            if i in used:\n",
    "                continue\n",
    "            checked=set()\n",
    "            p=i\n",
    "            lastp=None\n",
    "            judge=1 if nums[i]>0 else -1\n",
    "            while p not in checked:\n",
    "                checked.add(p)\n",
    "                used.add(p)\n",
    "                if (nums[p]>0 and judge==-1) or (nums[p]<=0 and judge==1):\n",
    "                    break\n",
    "                lastp=p\n",
    "                p=(p+nums[p])%len(nums)\n",
    "            if p in checked and not((nums[p]>0 and judge==-1) or (nums[p]<=0 and judge==1)) and lastp!=p:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def circularArrayLoop(self, nums: list[int]) -> bool:\r\n",
    "        \r\n",
    "        l = len(nums)\r\n",
    "        for i in range(l):\r\n",
    "            if nums[i] == 0:\r\n",
    "                continue\r\n",
    "            cur = set()\r\n",
    "            while True:\r\n",
    "                cur.add(i)\r\n",
    "                n = nums[i]\r\n",
    "                if n % l == 0:\r\n",
    "                    break\r\n",
    "                i = (n + i) % l\r\n",
    "                if (nums[i] == 0) or (n > 0 and nums[i] < 0) or (n < 0 and nums[i] > 0):\r\n",
    "                    break\r\n",
    "\r\n",
    "                if i in cur:\r\n",
    "                    return True\r\n",
    "                n = nums[i]\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "        return False\r\n",
    "                \r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums) -> bool:\n",
    "\n",
    "        self.n = len(nums)\n",
    "        self.nums = nums\n",
    "        for i in range(self.n):\n",
    "            self.direction = True if nums[i] > 0 else False\n",
    "            if self.slove(i):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def slove(self, idx):\n",
    "        num = self.nums[idx]\n",
    "        if num == 0:\n",
    "            return True\n",
    "        if abs(num) % self.n == 0:\n",
    "            return False\n",
    "        # if idx == 1:\n",
    "        #     print(idx,num,num>0,self.direction,(num>0) != self.direction)\n",
    "        if (num > 0) != self.direction:\n",
    "            return False\n",
    "        next_idx = (idx + num) % self.n\n",
    "\n",
    "        temp = num\n",
    "        self.nums[idx] = 0\n",
    "        ans = self.slove(next_idx)\n",
    "        if ans:\n",
    "            return ans\n",
    "        self.nums[idx] = temp\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def checkok(cur_idx):\n",
    "            checked = set()\n",
    "            checked.add(cur_idx)\n",
    "            st = None\n",
    "            if nums[cur_idx] > 0:\n",
    "                st = 1\n",
    "            else:\n",
    "                st = -1\n",
    "            while True:\n",
    "                nextidx = nums[cur_idx]\n",
    "                nextidx = (cur_idx + nextidx) % len(nums)\n",
    "                if nextidx == cur_idx:\n",
    "                    return False, checked\n",
    "                if st == 1 and nums[nextidx] < 0:\n",
    "                    return False, checked\n",
    "                if st == -1 and nums[nextidx] > 0:\n",
    "                    return False, checked\n",
    "                if nextidx in checked:\n",
    "                    return True, checked\n",
    "                checked.add(nextidx)\n",
    "                cur_idx = nextidx\n",
    "\n",
    "        used = set()\n",
    "        for i in range(len(nums)):\n",
    "            if i in used:\n",
    "                continue\n",
    "            ret, checked = checkok(i)\n",
    "            if ret:\n",
    "                return True\n",
    "            for x in checked:\n",
    "                used.add(x)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        length = len(nums)\n",
    "        visited = [-1] * length\n",
    "\n",
    "        for be in range(length):\n",
    "            if visited[be] != -1:\n",
    "                continue\n",
    "            #基于be开始向下移动\n",
    "            cur = be\n",
    "            while 1:\n",
    "                if visited[cur] != -1:\n",
    "                    if visited[cur] == be:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                visited[cur] = be\n",
    "                nxt = (nums[cur] + cur + length) % length\n",
    "                print(cur, nxt, end = \" \")\n",
    "                if nums[nxt] * nums[cur] < 0:\n",
    "                    break\n",
    "                elif nxt == cur:\n",
    "                    break\n",
    "                cur = nxt\n",
    "            \n",
    "            print(\"\")\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        has_been = set()\n",
    "        increase = 0\n",
    "        for i in range(len(nums)):  # for every element in array\n",
    "            while True:\n",
    "                if i in has_been:\n",
    "                    if increase >= len(nums) or increase <= -len(nums):\n",
    "                        return True\n",
    "                    break\n",
    "                has_been.add(i)\n",
    "                if (increase > 0 and nums[i] < 0) or (increase < 0 and nums[i] > 0):\n",
    "                    break\n",
    "                increase += nums[i]\n",
    "                next = (i + nums[i]) % len(nums)\n",
    "                if next == i:\n",
    "                    break\n",
    "                \n",
    "                i = next\n",
    "                \n",
    "            increase = 0\n",
    "            has_been = set()\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        for i in range(len(nums)):\n",
    "            if self.is_circle(nums, i):\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "    def is_circle(self, nums, start): #visible_set最后加\n",
    "        this_visible_set = set()\n",
    "        print(\"test\")\n",
    "        i = start + nums[start]\n",
    "        while i < 0:\n",
    "            i += len(nums)\n",
    "        i %= len(nums)\n",
    "        this_visible_set.add(start)\n",
    "\n",
    "        if i == start:\n",
    "            return False\n",
    "\n",
    "        if nums[start] > 0:\n",
    "            fu = 1\n",
    "        else:\n",
    "            fu = -1\n",
    "\n",
    "        while i not in this_visible_set:\n",
    "            print(i)\n",
    "            this_visible_set.add(i)\n",
    "            if fu == 1 and nums[i] < 0:\n",
    "                return False\n",
    "            if fu == -1 and nums[i] > 0:\n",
    "                return False\n",
    "            i += nums[i]\n",
    "            while i < 0:\n",
    "                i += len(nums)\n",
    "            i %= len(nums)\n",
    "        \n",
    "        index = i\n",
    "        i += nums[index]\n",
    "        while i < 0:\n",
    "            i += len(nums)\n",
    "        i %= len(nums)\n",
    "        if i == index:\n",
    "            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            history = {}\n",
    "            j = i\n",
    "            while j not in history:\n",
    "                history[j] = 1\n",
    "                next_idx = (j + nums[j]) % n\n",
    "                if nums[next_idx] * nums[j] < 0:\n",
    "                    j = next_idx\n",
    "                    break\n",
    "                j = next_idx\n",
    "            if j == i and (j + nums[j]) % n != i:\n",
    "                print(j)\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        # 用哈希\n",
    "        # 快慢指针\n",
    "        # n = len(nums)\n",
    "        # # 下一个位置\n",
    "        # nx = lambda x: (x+nums[x])%n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     if nums[i] == 0:continue\n",
    "        #     slow  = i\n",
    "        #     fast = nx(i)\n",
    "        #     while nums[slow]*nums[fast]>0 and nums[fast]*nums[nx(fast)]>0:\n",
    "        #         if slow == fast:\n",
    "        #             if slow == nx(slow):\n",
    "        #                 break\n",
    "        #             else:\n",
    "        #                 return True\n",
    "        #         slow = nx(slow)\n",
    "        #         fast = nx(nx(fast))\n",
    "        #     val = nums[i]\n",
    "        #     while val*nums[i] > 0:\n",
    "        #         tm = nx(i)\n",
    "        #         nums[i] = 0\n",
    "        #         i = tm\n",
    "        # return False\n",
    "\n",
    "\n",
    "\n",
    "        # 暴力 递归\n",
    "        # n = len(nums)\n",
    "        # # 取得下一个索引\n",
    "        # def get_next(cur, pos):\n",
    "        #     if pos:\n",
    "        #         return (cur+abs(nums[cur])) % n\n",
    "        #     return (cur-abs(nums[cur])) % n \n",
    "\n",
    "        # def dfs(cur, pos):\n",
    "        #     if cur == i and visit[cur] and get_next(cur, pos) != cur:\n",
    "        #         return True\n",
    "        #     if visit[cur] or (pos and nums[cur] < 0) or (not pos and nums[cur] > 0):\n",
    "        #         return False\n",
    "        #     visit[cur] = 1\n",
    "        #     return dfs(get_next(cur, pos), pos)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     visit = [0]*n \n",
    "        #     if dfs(i, nums[i] > 0):\n",
    "        #         return True\n",
    "        # return False\n",
    "\n",
    "\n",
    "        # 暴力+哈希\n",
    "        n = len(nums)\n",
    "        for srt, v in enumerate(nums):\n",
    "            if v:\n",
    "                jd, has = v > 0, set()\n",
    "                while srt not in has:\n",
    "                    if v == 0 or (v > 0) != jd: break\n",
    "                    nums[srt] = 0\n",
    "                    if v % n == 0: break\n",
    "                    has.add(srt)                   \n",
    "                    v = nums[(srt := (srt + v) % n)]\n",
    "                else: return True\n",
    "        return False\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def checkok(cur_idx):\n",
    "            checked = set()\n",
    "            checked.add(cur_idx)\n",
    "            st = None\n",
    "            if nums[cur_idx] > 0:\n",
    "                st = 1\n",
    "            else:\n",
    "                st = -1\n",
    "            while True:\n",
    "                nextidx = nums[cur_idx]\n",
    "                nextidx = (cur_idx + nextidx) % len(nums)\n",
    "                if nextidx == cur_idx:\n",
    "                    return False, checked\n",
    "                if st == 1 and nums[nextidx] < 0:\n",
    "                    return False, checked\n",
    "                if st == -1 and nums[nextidx] > 0:\n",
    "                    return False, checked\n",
    "                if nextidx in checked:\n",
    "                    return True, checked\n",
    "                checked.add(nextidx)\n",
    "                cur_idx = nextidx\n",
    "\n",
    "        used = set()\n",
    "        for i in range(len(nums)):\n",
    "            if i in used:\n",
    "                continue\n",
    "            ret, checked = checkok(i)\n",
    "            if ret:\n",
    "                return True\n",
    "            for x in checked:\n",
    "                used.add(x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "\n",
    "        def getNextIndex(i, nums) -> int:\n",
    "            i = i + nums[i]\n",
    "            while (i < 0):\n",
    "                i += len(nums)\n",
    "            return i % len(nums)\n",
    "\n",
    "        def reset(flag, nums) -> int:\n",
    "            print(flag)\n",
    "            for i in range(len(flag)):\n",
    "                nums[flag[i]] = 0\n",
    "\n",
    "        def check(i, nums) -> bool:\n",
    "            size = len(nums)\n",
    "            flag = [0] * len(nums)\n",
    "            loop = -1\n",
    "            visit = [i]\n",
    "            while (True):\n",
    "                if (nums[i] == 0):\n",
    "                    break\n",
    "                if (flag[i] == 1):\n",
    "                    loop = i\n",
    "                    break\n",
    "                flag[i] = 1\n",
    "                i = getNextIndex(i, nums)\n",
    "                visit.append(i)\n",
    "            if (loop == -1):\n",
    "                reset(visit, nums)\n",
    "                return False\n",
    "            \n",
    "            start = loop\n",
    "            count = 1\n",
    "            next = getNextIndex(loop, nums)\n",
    "            sign = -1\n",
    "            if (nums[start] > 0) :\n",
    "                sign = 1\n",
    "            while (True):\n",
    "                if (next == start):\n",
    "                    break\n",
    "                if (nums[next] * sign < 0):\n",
    "                    reset(visit, nums)\n",
    "                    return False\n",
    "                next = getNextIndex(next, nums)\n",
    "                count += 1\n",
    "            if (count == 1):\n",
    "                reset(visit, nums)\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        size = len(nums)\n",
    "        for i in range(size):\n",
    "            if (check(i, nums)):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*nums[i]<0:\n",
    "                            break\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = len(sign2)+1\n",
    "                        pos+=step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                    else:\n",
    "                        if sign2[pos]<len(sign2):\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        def next(cur: int) -> int:\n",
    "            return (cur + nums[cur]) % n  # 保证返回值在 [0,n) 中\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            slow, fast = i, next(i)\n",
    "            # 判断非零且方向相同\n",
    "            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:\n",
    "                print(slow, fast, nums[slow], nums[fast], nums[next(fast)])\n",
    "                if slow == fast:\n",
    "                    if slow == next(slow):\n",
    "                        break\n",
    "                    return True\n",
    "                slow = next(slow)\n",
    "                fast = next(next(fast))\n",
    "            add = i\n",
    "            while nums[add] * nums[next(add)] > 0:\n",
    "                tmp = add\n",
    "                add = next(add)\n",
    "                nums[tmp] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                direction = nums[i]-0\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*direction<0:\n",
    "                            break\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = len(sign2)+1\n",
    "                        pos = pos+step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                    else:\n",
    "                        if sign2[pos]<len(sign2):\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums) -> bool:\n",
    "        if len(nums) <=1 :return False\n",
    "        paths=[]\n",
    "        for i,v in enumerate(nums):\n",
    "            path=[]\n",
    "            path_real=[]\n",
    "            path.append(i)\n",
    "            path_real.append(v)\n",
    "            for i2 in range(len(nums)):\n",
    "                new_idx=path[-1]+nums[path[-1]]\n",
    "                #回到原点闭环退出\n",
    "                if (len(path)>1)&(path[-1]==path[0]):\n",
    "                    break\n",
    "                #正向达到列表最长长度\n",
    "                elif new_idx>=0:\n",
    "                    path.append(new_idx%len(nums)) \n",
    "                #逆向达到列表最长长度\n",
    "                elif new_idx<0:\n",
    "                    path.append(len(nums)+new_idx%-len(nums))  \n",
    "#                 print(path)\n",
    "                path_real.append(nums[path[-1]])\n",
    "            #去除闭环长度和输入长度相同且首位相同|去除同时包括正负|去除自循环\n",
    "            bol1=(len(path)==len(nums)+1)&(path[0]!=path[-1])\n",
    "            bol2= (any(i <0 for i in path_real) & any(i >0 for i in path_real))\n",
    "            bol3=len(path)<=2\n",
    "            print(bol1,bol2,bol3)\n",
    "            if bol1|bol2|bol3:\n",
    "                path=[]\n",
    "            else:\n",
    "                paths.append(path)\n",
    "#         print(paths)\n",
    "        paths.sort(reverse=True)\n",
    "        return   len(paths)>0\n",
    "nums=[2,-1,1,2,2]\n",
    "test=Solution()\n",
    "test.circularArrayLoop(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def checkok(cur_idx):\n",
    "            checked = set()\n",
    "            checked.add(cur_idx)\n",
    "            st = None\n",
    "            if nums[cur_idx] > 0:\n",
    "                st = 1\n",
    "            else:\n",
    "                st = -1\n",
    "\n",
    "            while True:\n",
    "                nextidx = nums[cur_idx]\n",
    "                nextidx = (cur_idx + nextidx) % len(nums)\n",
    "                if nextidx == cur_idx:\n",
    "                    return False, checked\n",
    "\n",
    "                if st == 1 and nums[nextidx] < 0:\n",
    "                    return False, checked\n",
    "                if st == -1 and nums[nextidx] > 0:\n",
    "                    return False, checked\n",
    "                if nextidx in checked:\n",
    "                    return True, checked\n",
    "                checked.add(nextidx)\n",
    "                cur_idx = nextidx\n",
    "\n",
    "        used = set()\n",
    "        for i in range(len(nums)):\n",
    "            if i in used:\n",
    "                continue\n",
    "            ret, checked = checkok(i)\n",
    "            if ret:\n",
    "                return True\n",
    "            for x in checked:\n",
    "                used.add(x)\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.circularArrayLoop([2, -1, 1, 2, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                if nums[i]>0:\n",
    "                    direction = 1\n",
    "                else:\n",
    "                    direction = -1\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                num = 0\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*direction<0:\n",
    "                            break\n",
    "                        num+=1\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = num\n",
    "                        pos = pos+step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                    else:\n",
    "                        if sign2[pos]<num:\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                if nums[i]>0:\n",
    "                    direction = 1\n",
    "                else:\n",
    "                    direction = -1\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*direction<0:\n",
    "                            break\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = len(sign2)+1\n",
    "                        pos = pos+step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                    else:\n",
    "                        if sign2[pos]<len(sign2):\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sign1 = set()\n",
    "        for i in range(n):\n",
    "            if i not in sign1:\n",
    "                if nums[i]>0:\n",
    "                    direction = 1\n",
    "                else:\n",
    "                    direction = -1\n",
    "                sign2 = {}\n",
    "                pos = i\n",
    "                num = 0\n",
    "                pre_num = 0\n",
    "                while 0<=pos<=n-1:\n",
    "                    if pos not in sign2:\n",
    "                        step = nums[pos]\n",
    "                        if step*direction<0:\n",
    "                            break\n",
    "                        num+=1\n",
    "                        sign1.add(pos)\n",
    "                        sign2[pos] = num\n",
    "                        pos = pos+step\n",
    "                        if pos<0 or pos>n-1:\n",
    "                            while pos<0:\n",
    "                                pos+=n\n",
    "                            while pos>n-1:\n",
    "                                pos-=n\n",
    "                            if pre_num == len(sign2):\n",
    "                                break\n",
    "                            pre_num = len(sign2)  \n",
    "                    else:\n",
    "                        if sign2[pos]<num:\n",
    "                            return True\n",
    "                        else:\n",
    "                            break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, pre_pos, pos, flag, nums):\n",
    "        # print(pre_pos, pos, nums, flag)\n",
    "        if pre_pos == pos:\n",
    "            return False\n",
    "        if isinstance(nums[pos], bool):\n",
    "            return nums[pos]\n",
    "        # print(nums[pos]*nums)\n",
    "        if nums[pos]*flag<=0:\n",
    "            return False\n",
    "        else:\n",
    "            step = nums[pos]\n",
    "            nums[pos]=True\n",
    "            tmp = self.dfs(pos, (pos+step)%len(nums), flag, nums)\n",
    "            nums[pos] = tmp\n",
    "            return tmp\n",
    "\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            if not isinstance(nums[i],bool):\n",
    "                flag = nums[i]\n",
    "                tmp = self.dfs(None, i, flag, nums)\n",
    "                if tmp:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, isDirected: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - isDirected: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    depth = [0] * n\n",
    "    startDeg = 0 if isDirected else 1\n",
    "    deg = [0] * n\n",
    "    if isDirected:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "                deg[u] += 1\n",
    "\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "class Solution:\n",
    "        def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "            def getNext(i: int) -> int:\n",
    "                return (i + nums[i]) % n\n",
    "\n",
    "            n = len(nums)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            deg = [0] * n\n",
    "            for i in range(n):\n",
    "                j = getNext(i)\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if nums[i] * nums[j] > 0:\n",
    "                    adjList[i].append(j)\n",
    "                    deg[j] += 1\n",
    "            cycles, *_ = cyclePartition(n, adjList, isDirected=True)\n",
    "            return any(len(g) > 1 for g in cycles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        self.nums = nums\n",
    "        for i in range(len(nums)):\n",
    "            direct = 1 if nums[i] > 0 else -1\n",
    "            if self.dfs(i,set(),direct):\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "\n",
    "    def dfs(self,index,seen,direct):\n",
    "        if abs(self.nums[index]) % len(self.nums) == 0 or self.nums[index]*direct < 0:\n",
    "            return False\n",
    "        nxt = (index + self.nums[index])%len(self.nums)\n",
    "        if nxt in seen:\n",
    "            return True\n",
    "        seen.add(index)\n",
    "        return self.dfs(nxt,seen,direct)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularArrayLoop(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        combine = []\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            _ = self.dfs(nums,combine[::],res,i)\n",
    "            # if len(res) > 0:\n",
    "            #     # return True\n",
    "        print(res)\n",
    "        if len(res) > 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def dfs(self,nums,combine,res,p):\n",
    "        if len(combine) == 0:\n",
    "            combine.append(p)\n",
    "            self.dfs(nums,combine,res,p+nums[p])\n",
    "        else:\n",
    "            if abs(p) > len(nums) -1:\n",
    "                p = p % len(nums)\n",
    "            if nums[p] * nums[combine[0]] < 0:\n",
    "                return \n",
    "            elif p in combine:\n",
    "                if len(combine) == 1:\n",
    "                    return \n",
    "                else:\n",
    "                    combine.append(p) # 确保p 不是最后一个\n",
    "                    if self.check_combine(combine,len(nums)):\n",
    "                        res.append(combine[::])\n",
    "                    return\n",
    "            else:\n",
    "                combine.append(p)\n",
    "                self.dfs(nums,combine,res,p+nums[p])\n",
    "\n",
    "        return\n",
    "\n",
    "    def check_combine(self,ls,n):\n",
    "        ls = [x  if x >=0 else x+n for x in ls]\n",
    "        for i in range(1,len(ls)):\n",
    "            if ls[i] == ls[i-1]:\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def circularArrayLoop(self, nums: list[int]) -> bool:\r\n",
    "        \r\n",
    "        l = len(nums)\r\n",
    "        visited = set()\r\n",
    "        for i in range(l):\r\n",
    "            if i in visited:\r\n",
    "                continue\r\n",
    "            cur = set()\r\n",
    "            while True:\r\n",
    "                cur.add(i)\r\n",
    "                visited.add(i)\r\n",
    "                n = nums[i]\r\n",
    "                if n % l == 0:\r\n",
    "                    break\r\n",
    "                i = (n + i) % l\r\n",
    "                if (n > 0 and nums[i] < 0) or (n < 0 and nums[i] > 0):\r\n",
    "                    break\r\n",
    "                if i in cur:\r\n",
    "                    return True\r\n",
    "                if i in visited:\r\n",
    "                    break\r\n",
    "                n = nums[i]\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "        return False\r\n",
    "                \r\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
